package com.zjsru.plan2023.oneday;

/**
 * @Author: cookLee
 * @Date: 2023-11-21
 * 美化数组的最少删除数
 * nums.length 为偶数
 * 对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立
 */
public class MinDeletion {

    /**
     * 主
     * \
     * 输入：nums = [1,1,2,3,5]
     * 输出：1
     * 解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。
     * \
     * 输入：nums = [1,1,2,2,3,3]
     * 输出：2
     * 解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinDeletion minDeletion = new MinDeletion();
        int[] nums = new int[]{1, 1, 2, 3, 5};
        System.out.println(minDeletion.minDeletion(nums));
    }

    /**
     * 最小删除
     *
     * @param nums nums
     * @return int
     */
    public int minDeletion(int[] nums) {
        int ans = 0;
        int len = nums.length;
        //变量记录当前的下标时偶数还是奇数
        boolean valid = true;
        for (int i = 0; i + 1 < len; i++) {
            if (nums[i] == nums[i + 1] && valid) {
                ans++;
            } else {
                valid = !valid;
            }
        }
        //len-ans模拟删减后的数据，如果数量不是偶数则需要多删一次 相当于ans+1
        if ((len - ans) % 2 != 0) {
            ans++;
        }
        return ans;
    }

    /**
     * 最小删除2
     *
     * @param nums nums
     * @return int
     */
    public int minDeletion2(int[] nums) {
        int ans = 0;
        //每次走两步，放弃第一种版本的valid奇数偶数变量
        for (int i = 0; i < nums.length; i += 2) {
            //下标i在最后一个，代表(处理后)的数组长度为奇数，需要把最后一个元素删除，即相当于ans+1，保证偶数
            if (i == nums.length - 1) {
                ans++;
                return ans;
            }
            //如果当前下表元素和下一个相等，就删除一个，即ans+1，同时将下标-1 来模拟删除后只剩一个的情况
            if (nums[i] == nums[i + 1]) {
                ans++;
                i--;
            }
        }
        //偶数状态下直接返回即可
        return ans;
    }
}
